"""
=================================================
@Author: Zhenzhou Liu
@Date: 2024/7/17 19:36
@Desc:
==================================================
"""
import collections
from collections import deque
from typing import List

from tree import TreeNode


class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]
        que = deque([(entrance[0], entrance[1], 0)])
        maze[entrance[0]][entrance[1]] = '+'

        while que:
            x, y, d = que.popleft()
            for i in range(4):
                new_x = x + dx[i]
                new_y = y + dy[i]
                if new_x >= 0 and new_x < m and new_y >= 0 and new_y < n and maze[new_x][new_y] == '.':
                    if new_x == 0 or new_x == m - 1 or new_y == 0 or new_y == n - 1:
                        return d + 1
                    que.append((new_x, new_y, d + 1))
                    maze[new_x][new_y] = '+'

        return -1


    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        que = deque([])
        isLand = deque([])
        dx = [-1, 0, 1, 0]
        dy = [0, -1, 0, 1]

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    que.append((i, j))
                    grid[i][j] = -1

                    while que:
                        x, y = que.popleft()
                        isLand.append((x, y))

                        for k in range(4):
                            new_x = x + dx[k]
                            new_y = y + dy[k]
                            if 0 <=  new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 1:
                                que.append((new_x, new_y))
                                grid[new_x][new_y] = -1


                    step = 0
                    while isLand:
                        level_size = len(isLand)

                        for k in range(level_size):
                            x, y = isLand.popleft()

                            for m in range(4):
                                new_x = x + dx[m]
                                new_y = y + dy[m]
                                if 0 <=  new_x < n and 0 <= new_y < n:
                                    if grid[new_x][new_y] == 1:
                                        return step
                                    elif grid[new_x][new_y] == 0:
                                        isLand.append((new_x, new_y))
                                        grid[new_x][new_y] = -1

                        step += 1

        return 0


    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        if startGene == endGene:
            return 0

        def diff_one(s: str, t: str) -> bool:
            return sum(x != y for x, y in zip(s, t)) == 1

        m = len(bank)
        adj = [[] for _ in range(m)]
        end_index = -1

        for i, s in enumerate(bank):
            if s == endGene:
                end_index = i
            for j in range(i + 1, m):
                if diff_one(s, bank[j]):
                    adj[i].append(j)
                    adj[j].append(i)

        if end_index == -1:
            return -1

        que = [i for i, s in enumerate(bank) if diff_one(s, startGene)]
        visited = set(que)
        que = deque(que)
        step = 1
        while que:
            level_size = len(que)
            for i in range(level_size):
                cur = que.popleft()
                if cur == end_index:
                    return step
                for next in adj[cur]:
                    if next not in visited:
                        que.append(next)
                        visited.add(next)
            step += 1

        return -1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

        def add_word(word: str):
            nonlocal node_num
            if word not in word_id:
                word_id[word] = node_num
                node_num += 1

        def add_edge(word: str):
            add_word(word)
            id1 = word_id[word]
            chars = list(word)
            for i in range(len(chars)):
                tmp = chars[i]
                chars[i] = '*'
                new_word = str(chars)
                add_word(new_word)
                id2 = word_id[new_word]
                edges[id1].append(id2)
                edges[id2].append(id1)
                chars[i] = tmp

        node_num = 0
        word_id = dict()
        edges = collections.defaultdict(list)

        for word in wordList:
            add_edge(word)

        add_edge(beginWord)
        if endWord not in wordList:
            return 0

        dis = [float('inf')] * node_num
        beginId, endId = word_id[beginWord], word_id[endWord]
        dis[beginId] = 0

        que = collections.deque([beginId])
        while que:
            x = que.popleft()
            if x == endId:
                return dis[endId] // 2 + 1
            for it in edges[x]:
                if dis[it] == float('inf'):
                    dis[it] = dis[x] + 1
                    que.append(it)

        return 0

    def canReach(self, arr: List[int], start: int) -> bool:
        if arr[start] == 0:
            return True
        que = collections.deque([start])
        visited = {start}
        length = len(arr)

        while que:
            cur = que.popleft()
            next = [cur + arr[cur], cur - arr[cur]]
            for it in next:
                if 0 <= it < length and it not in visited:
                    if arr[it] == 0:
                        return True
                    que.append(it)
                    visited.add(it)

        return False


    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        # error: use shallow copy.
        # dist = [[100000] * n] * m
        dist = [[100000] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0

        for i in range(m):
            for j in range(n):
                newI = i - 1
                newJ = j - 1
                if newI >= 0:
                    dist[i][j] = min(dist[i][j], dist[newI][j] + 1)
                if newJ >= 0:
                    dist[i][j] = min(dist[i][j], dist[i][newJ] + 1)

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                newI = i + 1
                newJ = j + 1
                if newI < m:
                    dist[i][j] = min(dist[i][j], dist[newI][j] + 1)
                if newJ < n:
                    dist[i][j] = min(dist[i][j], dist[i][newJ] + 1)

        return dist

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] == 1:
            return -1
        n = len(grid)
        dist = [[1000] * n for _ in range(n)]
        dist[0][0] = 1

        queue = deque([(0, 0)])
        while queue:
            x, y = queue.popleft()
            if x == n - 1 and y == n - 1:
                return dist[x][y]
            for dx in range(-1, 2):
                for dy in range(-1, 2):
                    newX = x + dx
                    newY = y + dy
                    if newX < 0 or newX >= n or newY < 0 or newY >= n:
                        continue
                    if grid[newX][newY] == 1 or dist[newX][newY] <= dist[x][y] + 1:
                        continue
                    dist[newX][newY] = dist[x][y] + 1
                    queue.append((newX, newY))
        return -1

    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        parent = collections.defaultdict(lambda: None)
        ans = []

        def findParents(root: TreeNode):
            if root.left is not None:
                parent[root.left.val] = root
                findParents(root.left)
            if root.right is not None:
                parent[root.right.val] = root
                findParents(root.right)

        def findAns(prev: TreeNode, node: TreeNode, depth: int):
            if node is None:
                return
            if depth == k:
                ans.append(node.val)
                return
            if node.left != prev:
                findAns(node, node.left, depth + 1)

            if node.right != prev:
                findAns(node, node.right, depth + 1)

            if parent[node.val] != prev:
                findAns(node, parent[node.val], depth + 1)

        findParents(root)
        findAns(None, target, 0)
        return ans


    def shortestPathAllKeys(self, grid: List[str]) -> int:
        direction = [[-1, 0], [0, -1], [0, 1], [1, 0]]
        sx, sy = 0, 0
        key_to_id = dict()
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                ch = grid[i][j]
                if ch == '@':
                    sx = i
                    sy = j
                elif ch.islower():
                    if ch not in key_to_id:
                        id = len(key_to_id)
                        key_to_id[ch] = id

        que = deque([(sx, sy, 0)])
        dist = dict()
        dist[(sx, sy, 0)] = 0
        key_size = len(key_to_id)

        while que:
            old_index = que.popleft()
            x, y, mask = old_index
            for dx, dy in direction:
                nx, ny = x + dx, y + dy
                if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][ny] != '#':
                    ch = grid[nx][ny]
                    if ch == '.' or ch == '@':
                        index = (nx, ny, mask)
                        if index not in dist:
                            dist[index] = dist[old_index] + 1
                            que.append(index)

                    elif ch.islower():
                        idx = key_to_id[ch]
                        new_mask = mask | 1 << idx
                        index = (nx, ny, new_mask)
                        if index not in dist:
                            dist[index] = dist[old_index] + 1
                            if new_mask == (1 << key_size) - 1:
                                return dist[index]
                            que.append(index)

                    else:
                        idx = key_to_id[ch.lower()]
                        key = mask & 1 << idx
                        index = (nx, ny, mask)
                        if key and index not in dist:
                            dist[index] = dist[old_index] + 1
                            que.append(index)

        return -1


if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    root.left.right.left = TreeNode(7)
    root.left.right.right = TreeNode(7)
    solution = Solution()
    print(solution.distanceK(root, root.left, 2))
